package com.dylan.历史.领扣;

/**
 * @Auther: ankang
 * @Date: 2019/2/25 20:18
 * @Description:
 */
public class $0064最小路径和 {

    public static void main(String[] args) {
        int[][] grid = new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        new Solution().minPathSum(grid);
    }

    static class Solution {
        public int minPathSum(int[][] grid) {
            int m = grid.length;
            if(m == 0) {
                return 0;
            }
            int n = grid[0].length;
            if(n == 0) {
                return 0;
            }
            int[][] route = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0 && j == 0) {
                        route[0][0] = grid[0][0];
                        continue;
                    }
                    int temp1 = -1;
                    int temp2 = -1;
                    if (i > 0) {
                        temp1 = route[i - 1][j] + grid[i][j];
                    }
                    if (j > 0) {
                        temp2 = route[i][j - 1] + grid[i][j];
                    }
                    if (temp1 == -1 && temp2 != -1) {
                        route[i][j] = temp2;
                    } else if (temp1 != -1 && temp2 == -1) {
                        route[i][j] = temp1;
                    } else {
                        route[i][j] = temp1 > temp2 ? temp2 : temp1;
                    }
                }
            }
            return route[m - 1][n - 1];
        }
    }
}
